var free_space = '.';
var obstacle = '*';
var goal = 'A';

var iter = 0;
var running = 0;
var interval;
var positions = {};
var paths = [];
var min = null;


//the solver function
// takes the levelstring as input
function solve(lvl)
{
    if (!lvl)
        lvl = levels[level-1].levelstring;
    positions = {};
    positions[lvl] = {levelstring: lvl, nrmoves: 0, solved: false, parent: null, move: null};
    paths = [];
    iter = 0;
    min = null;
    ////////////////////////////
    var moves = moveslist(lvl);
    var i;
    for (i=0; i < moves.length; i++)
    {
        paths.push({levelstring: lvl, move: moves[i], nrmoves: 0});
    }
    //////////////////
    tryMoves();
    //////////////////
    
    var minumum = Number.MAX_VALUE;
    var index = null;
    for (i in positions)
    {
        if (positions[i].solved && positions[i].nrmoves < minumum)
        {
            index = i;
            minumum = positions[i].nrmoves;
        }
    }
    var solution = [];
    if (index)
    {
        while (positions[index].parent)
        {
            solution.push(positions[index].move);
            index = positions[index].parent;
        }
    }
    updateStatus(solution);
    return solution;
}

function tryMoves()
{
    while (paths.length)
    {
        iter++;
        var path = paths.shift();
        var nrmoves = path.nrmoves + 1;
        
        if (min && nrmoves > min)
            continue;
            
        var lvl = applyMove(path.levelstring, path.move);
        var isSolved = solved(lvl);
        var found = false;
        var faster = true;
        
        //check if this position was reached by another path
        var p = positions[lvl];
        if (p)
        {
            if (p.nrmoves > nrmoves)
            {
                p.parent = path.levelstring;
                p.nrmoves = nrmoves;
                p.move = path.move;
                p.solved = isSolved;
            }
            else
            {
                faster = false;
            }
        }
        else
        {
            positions[lvl] = {levelstring: lvl, parent: path.levelstring, nrmoves: nrmoves, move: path.move, solved: isSolved};
        }
        
        //if this path was faster and it's not a solution then explore other paths leading from here
        if (faster && !isSolved)
        {
            var moves = moveslist(lvl, path.move);
            for (var i=0; i < moves.length; i++)
            {
                paths.push({levelstring: lvl, move: moves[i], nrmoves: nrmoves});
            }
        }
        
        //if a solution was found, all other paths that have higher number of moves are worst possible solutions so they are removed
        if (isSolved)
        {
            min = nrmoves;
            var index = 0;
            while(index < paths.length)
            {
                if (paths[index].nrmoves > nrmoves)
                    paths.splice(index, 1);
                else
                    index++;
            }
        }
        if (paths.length == 0)
            break;
    }
}

function updateStatus(solution)
{
    if (solution.length)
    {
        $('#solution').html(solution.reverse().join().fixed());
    }
    else
    {
        $('#solution').text('unsolvable');
    }
}

//checks if there is a goal block on the last line(6 chars) of the levelstring
function solved(levelstring)
{
    for (var i = 0; i < 6; i++)
    {
        if (levelstring.charAt(30 + i) == goal)
            return true;
    }
    return false;
}


//returns an array with unique elements
Array.prototype.unique = function()
{
    var o = {}, i, l = this.length, r = [];
    for(i=0; i<l;i++) 
        o[this[i]] = this[i];
    for(i in o) 
        r.push(o[i]);
    return r;
}


//generates an array of possible moves from a levelstring
//it may receive the previous move and elliminate it from the list
function moveslist(levelstring, move)
{
    if (move)//find the opposite move
    {
        var newMove = move.split('');
        var dir = '';
        switch(newMove[1])
        {
            case 'u':
                newMove[1] = 'd';
                break;
            case 'd':
                newMove[1] = 'u';
                break;
            case 'l':
                newMove[1] = 'r';
                break;
            case 'r':
                newMove[1] = 'l';
                break;
        }
        move = newMove.join('');
    }
    
    var lvl = levelstring.split('');
    var moves = [];
    for (var i = 0; i < 6; i++)
        for (var j = 0; j < 6; j++)
        {
            var index = i*6 + j;
            var block = lvl[index];
            if (block >= 'a' && block <= 'z') //horizontal
            {
                //try left
                var hindex = j-1;
                while(hindex >= 0 && lvl[i*6 + hindex] == free_space)
                {
                    var m = block + 'l' + (j-hindex);
                    if (m != move)
                        moves.push(m);
                    hindex--;
                }
                //try right
                hindex = j+1;
                while(hindex < 6 && lvl[i*6 + hindex] == free_space)
                {
                    var m = block + 'r' + (hindex-j);
                    if (m != move)
                        moves.push(m);
                    hindex++;
                }
            }
            else if (block >= 'A' && block <= 'Z') //vertical
            {
                //try up
                var vindex = i-1;
                while(vindex >= 0 && lvl[vindex*6 + j] == free_space)
                {
                    var m = block + 'u' + (i-vindex);
                    if (m != move)
                        moves.push(m);
                    vindex--;
                }
                //try down
                vindex = i+1;
                while(vindex < 6 && lvl[vindex*6 + j] == free_space)
                {
                    var m = block + 'd' + (vindex-i);
                    if (m != move)
                        moves.push(m);
                    vindex++;
                }
            }
        }
        return moves;
}


//applies a move to a levelstring
//  - lvl = the string representing the level
//  - move = a 3 character string: the block letter, the direction(u d l r), number of steps to take
function applyMove(lvl, move)
{
    levelstring = lvl.split('');
    var block = move.charAt(0);
    var direction = move.charAt(1);
    var steps = parseInt(move.charAt(2));
    if (direction == 'l' || direction == 'u') 
        for (i = 0; i < 6; i++)
            for (j = 0; j < 6; j++)
            {
                var index = 6*i + j;
                if (levelstring[index] == block)
                {
                    if (direction == 'l')
                    {
                        levelstring[index-steps] = levelstring[index];
                        levelstring[index] = free_space;
                    }
                    else if (direction == 'u')
                    {
                        levelstring[index - 6*steps] = levelstring[index];
                        levelstring[index] = free_space;
                    }
                }
            }
    else
        for (i = 6-1; i >= 0; i--)
            for (j = 6-1; j >= 0; j--)
            {
                var index = 6*i + j;
                if (levelstring[index] == block)
                {
                    if (direction == 'r')
                    {
                        levelstring[index+steps] = levelstring[index];
                        levelstring[index] = free_space;
                    }
                    else if (direction == 'd')
                    {
                        levelstring[index + 6*steps] = levelstring[index];
                        levelstring[index] = free_space;
                    }
                }
            }
    return levelstring.join('');
}